Threshold Ed25519 Signatures

Talk Outline

1. Definitions and Concepts
2. Ed25519
3. Ed25519 Complications for Threshold Signatures
4. Current Standardisation Drafts
5. The TIDE System for Threshold Ed25519 Signatures

Elliptic Curve Cyptography Overview

For the purposes of cryptography, an elliptic curve is any one of the following forms:

• \( y^2 = x^3 + ax + b \) (a Weierstrass curve)
• \( by^2 = x^3 + ax^2 + x \) (a Montgomery curve)
• \( ax^2 + y^2 = 1 + dx^2y^2 \) (a Twisted Edwards curve)

Where \( x, y \) are unknowns in some field \( \FF \) and \(a \), \( b \), and \( d \) are constants in the same field.

The field \( \FF \) is usually a finite field \( \ZZ_p \) (or, equivalently, \( \mathit{GF}(p) \)) for some prime \( p \).

Given any two points \( \cvPt{P}_1, \cvPt{P}_2 \in E(\FF) \) there is a method of adding \( \cvPt{P}_1 \) and \( \cvPt{P}_2 \) to find a new point \( \cvPt{P}_1 + \cvPt{P}_2 \in E(\FF) \).

The set \( E(\FF) \) with this addition method forms a group with all that entails.

Of particular interest in this talk is the group associativity property: \[ \left( \cvPt{P}_1 + \cvPt{P}_2 \right) + \cvPt{P}_3 = \cvPt{P}_1 + \left( \cvPt{P}_2 + \cvPt{P}_3 \right) \quad \forall \, \cvPt{P}_1, \cvPt{P}_2, \cvPt{P}_3 \in E(\FF) \]

There is a natural action of the integers on this group wherein given \( k \in \ZZ \): \[ k\cvPt{P} := \underbrace{\cvPt{P} + \cvPt{P} + \dotsb + \cvPt{P}}_{k\text{ times}} \] Note: this action has a distributive property: \( (k_1 + k_2)\cvPt{P} = k_1\cvPt{P} + k_2\cvPt{P} \).

The hardness of this problem is the basis of the security of elliptic curve cryptography.

Shamir Secret Sharing

A secret \( s \in \ZZ_p \) can be shared in a \( t \)-in-\( n \) sharing scheme wherein \( n \) actors have shares of the secret and any \( t \) or more may combine their shares by:

• Randomly generating an degree \( t-1 \) polynomial \( P \) such that \( P(0) = s \)
• Give each of the \( n \) actors a share \( \sigma_i = \left(x_i, P(x_i)\right) \).

Any subset of shares \( \left\{ \sigma_c \mid c \in C \subset \left\{1,\dotsc,n\right\}\right\} \) (where \( \lvert C \rvert \ge t \)) can resconstruct the secret by \[ s = \sum_{c \in C} P\left(x_c\right) l_c(C) \quad\text{where}\quad l_i(C) = \prod_{c\in C, c \ne i} \frac{x_c}{x_c - x_i} \]

c.f. “How to Share a Secret” by Adi Shamir in Commun. ACM November 1979

Threshold Signatures

Such a signature might be composed of otherwise valid signatures.

Individual contributions can be combined directly, or via Shamir secret sharing.

Ed25519

For reference:

• S. Josefsson and I. Liusvaara.
  Edwards-curve digital signature algorithm (eddsa).
  RFC 8032. January 2017.
  Available at: https://datatracker.ietf.org/doc/html/rfc8032.
• Daniel J Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang.
  High-speed high-security signatures.
  Journal of Cryptographic Engineering, 2(2):77–89, 2012.
  Available at: https://ed25519.cr.yp.to/ed25519-20110926.pdf.

Ed25519

In the specific case of Ed25519 we use the twisted Edwards curve \[ E\left(\ZZ_p\right) = \left\{ (x,y) \in \ZZ_p^2 \mid x^2 + y^2 = 1 + \tfrac{121665}{121666}x^2y^2 \right\} \] where \( p = 2^{255}-19 \).

Specifically, calculations are performed over the cyclic subgroup generated by the point \( \cvPt{G} = \left(x, \tfrac{4}{5}\right)\) with positive \( x \)-coordinate. This subgroup has prime order \[ \ell = 2^{252}+27,\!742,\!317,\!777,\!372,\!353,\!535,\!851,\!937,\!790,\!883,\!648,\!493 \]

Note: points in \( E(\FF_p) \) that are not in this cyclic subgroup must have order 1, 2, 4, or 8.

\( E(\FF_p) \) is bi-rationally equivalent to Curve25519 (a Mongtommery curve for key exchange).

CITATION NEEDED

Ed25519 Key Generation

To generate a public/private key pair for Ed25519 signing:

1. Generate 32 random bytes in a cryptographically secure manner.
   Call this \( s \), and refer to it as the “secret seed”.
2. Calculate \( h = \operatorname{SHA512}(s) \).
3. Split \( h \) into two halves.
   • \( H_1 = h_0, \dotsc, h_{255} \)
   • \( H_2 = h_{256}, \dotsc, h_{511} \)
   We refer to \( H_2 \) as the “signing prefix”.
4. Key Clamping:
   • Clear the bits \( h_0 \), \( h_1 \), \( h_2 \), and \( h_{255} \) in \( H_1 \). (i.e., set them to zero).
   • Set the bit \( h_{254} \) (i.e., set it to one).
5. Let \( a = \sum_{i=0}^{255} h_i 2^i \) (i.e., interpret \( H_1 \) as a number). We refer to this as the “secret scalar”.
6. We calculate the public key \( A = a\cvPt{G} \).

Note: \( a\cvPt{G} = (a \operatorname{mod} \ell)\cvPt{G} \).

Ed25519 Key Clamping

The bit manipulation (sometimes called “clamping”) of the bits of \( H_1 \) in step 4. guarantees that \( a \) is a multiple of 8.

This step is also peformed in the key generation for Curve25519 public keys where it provides an important protection against attacks in the key exchange using low order points outside of the cyclic group.

The reason for it in Ed25519 is not clear, and causes some difficulties in security proofs (see the CRYPTREC Investigation Reports on Cryptographic Techniques in FY 2020 — in particular Steven D. Galbraith's “CRYPTREC Review of EdDSA”).

We note in passing that clamping will have the effect of guaranteeing that all keys for Ed25519 are bi-rationally equivalent to valid keys for Curve25519.

Ed25519 Signing and Verification

Given a message, \( M \), we sign the message by:

1. Calculate \( \cvPt{R} = r\cvPt{G} \) where \( r = \operatorname{NUM}(H_2 \concat M) \).
2. Calculate \( k = \operatorname{NUM}(\cvPt{R} \concat \cvPt{A} \concat M) \).
3. Calculate \( S = (r+ka) \operatorname{mod} \ell \).
4. The signature is the pair \( \left( \cvPt{R}, S \right) \).

To verify a signature:

1. Verify that \( \cvPt{R} \) and \( \cvPt{A} \) correctly encode points, and that \( 0 \le S < \ell \).
2. Calculate \( k = \operatorname{NUM}(\cvPt{R} \concat \cvPt{A} \concat M) \).
3. Check that \( (8S)\cvPt{G} = 8\cvPt{R} + (8k)\cvPt{A} \).

Ed25519 for Threshold Signatures

We note that if \( (a_1, \cvPt{A_1}) \) and \( (a_2, \cvPt{A_2}) \) are valid Ed25519 key pairs (i.e., secret scalar and public key), then because of the associative property of curve addition: \[ (a_1 + a_2)\cvPt{G} = a_1\cvPt{G} + a_2 \cvPt{G} = \cvPt{A}_1 + \cvPt{A}_2 \] and so \( (a_1 + a_2, \cvPt{A}_1 + \cvPt{A}_2) \) is also a valid Ed25519 key pair.

Similarly, if in signing, if \( \cvPt{R_1} = r_1 \cvPt{G} \) and \( \cvPt{R_2} = r_2 \cvPt{G} \) then \( (r_1 + r_2) \cvPt{G} = R_1 + R_2 \).

If we fix \( k = \operatorname{NUM}(R_1 + R_2 \concat \cvPt{A} \concat M) \) then if \( S_1 = (r_1 + ka_1) \operatorname{mod} \ell \) and \( S_2 = (r_2 + k a_2) \operatorname{mod} \ell \) then \[ \begin{aligned} S_1 + S_2 &= (r_1 + ka_1) \operatorname{mod} \ell + (r_2 + k a_2) \operatorname{mod} \ell \\ &= (r_1 + ka_1 + r_2 + ka_2) \operatorname{mod} \ell &= \left( \left(r_1 + r_2\right) + k \left(a_1 + a_2\right) \right) \operatorname{mod} \ell \end{aligned} \]

Complications for Threshold Signatures

• There is no clear threshold signing prefix value.
  • Sum of individual signing prefixes is not the same as the signing prefix for the aggregate public key.
  • Deterministic nonce \( r \) might allow leaking of private key.
• Bit manipulations in key generation.
  • Distributive property of the group action mean that aggregate public keys will still be a multiple of 8.
  • Setting of 2nd-most significant bit makes it unclear if the aggregate key will still be a key that could be generated directly.
• Need to agree on value of \( k \) for signing.
  • Probably not an issue in practice; will require some communication.

Standardisation Drafts

There are currently two IETF drafts relating to threshold schemes for elliptic curves, both by P. M. Hallam-Baker

• “Threshold Modes in Elliptic Curves”
  • https://datatracker.ietf.org/doc/html/draft-hallambaker-threshold
  • A more broad description of threshold schemes for elliptic curves (including signing, key exchange, etc)
  • Focuses on Ed25519/X25519 and Ed448/X448.
• “Threshold Signatures in Elliptic Curves”
  • https://datatracker.ietf.org/doc/html/draft-hallambaker-threshold-sigs
  • Specifically covers threshold signature schemes for Ed25519 (and Ed448)
  • Strictly speaking, this draft expired in July 2021.

Hallam-Baker Drafts

• Gives a threshold threshold signing-method that works both directly and via Shamir secret sharing.
  • Two roles: “dealer” and “signer”. Dealer requests signatures (and controlls the flow), and signers perform signature.
• Points out several attacks.
  • Of particular note: the deterministic value of \( r \) when signing can be exploited by the dealer to potentially discover the signing keys of the signers. Recommends random generation instead.
• Notable absense of method to generate keys for Shamir secret sharing variant.
  • The section named “Distributed Key Generation” has content consisting of only “[TBS]”.

Hallam-Baker Signing Protocol

We assume that each signer, \( \Psi_i \) has a keypair \( (a_i, \cvPt{A}_i \) ).

1. Dealer selects and notifies signers, sends \( M \) to signers.
2. Each signer, \(\Psi_i\):
   1. Randomly genrates \( 1 < r_i < \ell \) and calculates \( \cvPt{R}_i = r_i \cvPt{G} \)
   2. Transmits \( \cvPt{R}_i \) to the dealer.
3. The dealer (perhaps at some later point) may complete the signature by:
   1. Calculating \( \cvPt{R} = \sum_i \cvPt{R}_i \)
   2. Calculating \( c_i \) for each \( \Psi_i \). \( c_i = \begin{cases} 1 & \text{for direct signatures} \\ l_i(C) & \text{ if Shamir secret sharing is used} \end{cases}\)
   3. Transmiting \( \cvPt{R} \), \( \cvPt{A} \), and \( c_i \) to each signer \( \Psi_i \).
4. The signers may complete their contributions by:
   1. Computing \( k = \operatorname{NUM}(\cvPt{R} \concat \cvPt{A} \concat M) \)
   2. Computing \( S_i = (r_i + k c_i a_i) \operatorname{mod} \ell \)
   3. Transmiting \( \cvPt{R}_i \) and \( S_i \) to the dealer.
5. The dealer completes the signature by:
   1. Computing \( S = \sum_i S_i \)
   2. Verifying that the signature \( (\cvPt{R}, S) \) is valid

TIDE System

• The TIDE system uses the same signing protocol as Hallam-Baker
• TIDE have solved the distributed key generation problem absent in the Hallam-Baker drafts, using the swarm random number generator described by Geetika.
• No actor—nether the user (the dealer), nor the ORKs (the signers and key generators)—ever sees or the aggregate secret scalar.
• The aggregate secret scalar is never stored.
• Signing is nonetheless possible becuse of the Shamir secret sharing implemented in the swarm random number generator.

TIDE Swarm Ed25519 Key Generation

1. The users selects \( n \) ORK's to generate the key and act as signers.
2. Each ORK, \( O_i \) generates
   • A secret scalar \( a_i \).
   • A \( t \)-in-\( n \) Shamir secret sharing polynomial \( P_i(x) \) to share secret \( a_i \)
   in addition, \( O_i \), also has a known unique (to the Swarm) \( x \)-coordinate, \( x_i \).
3. Each ORK, \( O_i \) calculates:
   • Public key \( \cvPt{A}_i = a_i\cvPt{G} \).
   • Shares \( (x_j, P_i(x_j)) \) of its secret scalar for all other ORKS, \( O_j \) in the swarm. These are encrypted.
   and transmits these to the user.
4. After receiving responses from all ORKs in the swarm, the user:
   1. Calculates \( \cvPt{A} = \sum_i \cvPt{A}_i \).
   2. Transmits to each ork, \( O_i \) the value \( \cvPt{A} \) and all shares \( (x_i, P_j(x_i) ) \) for that ORK.
5. Each ORK, \( O_i \) calculates it's share of the aggregate secret scalar \( \sigma_i = \left(x_i, \sum_{j=1}^n P_j(x_i)\right)\)

The aggregate secret scalar is \( a = \sum_{i=1}^n a_i \).